package main;

import java.util.*;

/**
 * @author zhx
 * <p>
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 * 满足要求的三元组集合为：
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 */
public class LeetCode15 {

    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        int low = 0;
        int high = nums.length - 1;
        int middle = high - 1;
        long beforeScan = System.currentTimeMillis();
        while ((nums[high] >= 0) && (low != middle)) {
            for (; low < middle; ) {
                //满足条件
                if ((nums[low] + nums[middle] + nums[high]) == 0) {
                    ArrayList<Integer> tmplist = new ArrayList<>();
                    tmplist.add(nums[low]);
                    tmplist.add(nums[middle]);
                    tmplist.add(nums[high]);
                    if (!result.contains(tmplist)) {
                        result.add(tmplist);
                    }
                }
                // 前两者之和大于高位值,
                if ((nums[low] + nums[middle] + nums[high]) > 0) {
                    middle--;//low++;
                } else {
                    low++;//middle--;
                }
            }
            high--;
            // 指针复位
            low = 0;
            middle = high - 1;
        }
        long afterScan_and_beforeHash = System.currentTimeMillis();
        Set<List<Integer>> set = new HashSet<>(result);
        long afterHash = System.currentTimeMillis();
        ArrayList<List<Integer>> result1 = new ArrayList<>();
        result1.addAll(set);
        System.out.println("time for scanning:" + (afterScan_and_beforeHash - beforeScan));
        System.out.println("time for hashing:" + (afterHash - afterScan_and_beforeHash));
        return result1;
    }
}
